/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#define MAXN 521
using namespace std;
/*-----------------------------------------------------------------------------*/
inline void File_Read() {
#ifndef MYLAB
	freopen("course.in", "r", stdin);
	freopen("course.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif
}

inline int get_num() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

int n, m, head[MAXN], dp[MAXN][MAXN], cnt, d[MAXN];
bool c[MAXN];

struct edge{
	int fr, to, ne;
	edge(){;}
	edge(int fr_, int to_, int ne_) {
		fr = fr_;
		to = to_;
		ne = ne_;
	}
}e[MAXN];

inline void add_edge(int fr, int to) {
	e[++cnt] = edge(fr, to, head[fr]), head[fr] = cnt;
}

void dfs(int x) { 
	for(int i = head[x]; i; i = e[i].ne) {
		int y = e[i].to;
		dfs(y);
		for(int j = n + 1; j > 1; j--) {
			for(int k = j - 1; k > 0; k--) {
				if(dp[x][j - k] + dp[y][k] > dp[x][j]) {
					dp[x][j] = dp[x][j - k] + dp[y][k];
				}
			}
		}
	}
}

//void get_road(int x, int k) {
//	for(int i = head[x]; i; i = e[i].ne) {
//		int y = e[i].to;
//		if(dp[x][k] == dp[y][k - 1] + dp[x][1]) {
//			c[y] = true;
//			get_road(y, k - 1);
//			return;
//		}
//	}
//}

int main() {
	File_Read();
	m = get_num();
	n = get_num();
	for(int i = 1; i <= m; i++) {
		int fr = get_num();
		dp[i][1] = get_num();
		add_edge(fr, i);
	}
	dfs(0);
	
	printf("%d\n", dp[0][n + 1]);
	
//	get_road(0, n + 1);
//	
//	for(int i = 1; i <= n; i++) {
//		if(c[i]) {
//			printf("%d\n", i);
//		}
//	}
	
	return 0;
}

